As an increasing number of applications and services are being made available over networks such as the Internet, an increasing number of content, application, and/or service providers are turning to technologies such as cloud computing. Cloud computing, in general, is an approach to providing access to electronic resources through services, such as Web services, where the hardware and/or software used to support those services is dynamically scalable to meet the needs of the services at any given time. A customer typically will rent, lease, or otherwise pay for access to resources through the cloud, such that the customer does not have to purchase and maintain the hardware and/or software to provide access to these resources. A potential disadvantage to such an approach, at least from a customer point of view, is that the resources typically are at a location under control of the provider of those resources, and thus are out of the direct control of the customer. In order to help ensure that resources allocated to the customer perform tasks only under direction of that customer, the provider environment can support request authentication to prevent unauthorized parties from accessing the resources. Such a service might include a multi-tenant key management service that maintains and manages one or more cryptographic keys owned by a customer. It is often the case, however, that customers would like some assurance that the service provider can guarantee against unauthorized access to the customer's data. This can include, for example, complying with lawful order to disclose data stored by the service provider, which can result in the keys and underlying data being exposed.